class TreeNode:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        self.count = 1


class Solution(object):
    def countPairs(self, nums, low, high):
        root = TreeNode(-1)
        for num in nums:
            node = root
            for i in range(14, -1, -1):
                val = (num >> i) & 1
                if val in node.neighbors:
                    node = node.neighbors[val]
                    node.count += 1
                else:
                    new_node = TreeNode(val)
                    node.neighbors[val] = new_node
                    node = new_node

        def find1(num, node, i):
            ans = 0
            if i < 0:
                return node.count * (node.count - 1) // 2
            if (num >> i) & 1:
                if 0 in node.neighbors:
                    ans += node.neighbors[0].count * (node.neighbors[0].count - 1) // 2
                if 1 in node.neighbors:
                    ans += node.neighbors[1].count * (node.neighbors[1].count - 1) // 2
                if 0 in node.neighbors and 1 in node.neighbors:
                    ans += find2(num, node.neighbors[0], node.neighbors[1], i - 1)
            else:
                if 0 in node.neighbors:
                    ans += find1(num, node.neighbors[0], i - 1)
                if 1 in node.neighbors:
                    ans += find1(num, node.neighbors[1], i - 1)
            return ans

        def find2(num, node1, node2, i):
            ans = 0
            if i < 0:
                return node1.count * node2.count
            if (num >> i) & 1:
                if 0 in node1.neighbors and 0 in node2.neighbors:
                    ans += node1.neighbors[0].count * node2.neighbors[0].count
                if 1 in node1.neighbors and 1 in node2.neighbors:
                    ans += node1.neighbors[1].count * node2.neighbors[1].count
                if 0 in node1.neighbors and 1 in node2.neighbors:
                    ans += find2(num, node1.neighbors[0], node2.neighbors[1], i - 1)
                if 1 in node1.neighbors and 0 in node2.neighbors:
                    ans += find2(num, node1.neighbors[1], node2.neighbors[0], i - 1)
            else:
                if 0 in node1.neighbors and 0 in node2.neighbors:
                    ans += find2(num, node1.neighbors[0], node2.neighbors[0], i - 1)
                if 1 in node1.neighbors and 1 in node2.neighbors:
                    ans += find2(num, node1.neighbors[1], node2.neighbors[1], i - 1)
            return ans
        return find1(high, root, 14) - find1(low - 1, root, 14)

data = Solution()
nums = [7,4,2,1]
low = 2
high = 6
print(data.countPairs(nums, low, high))